package com.peng.leetcode.tree;

import java.util.HashMap;
import java.util.Map;

/**
 * BuildTree1
 * 剑指 Offer 07. 重建二叉树
 * https://leetcode.cn/problems/zhong-jian-er-cha-shu-lcof/
 * <p>
 * Created on 2022/11/19
 *
 * @author lupeng
 */
public class BuildTree1 {

    public static void main(String[] args) {
        int[] pre = new int[]{3, 9, 20, 15, 7};
        int[] in = new int[]{9, 3, 15, 20, 7};
        new BuildTree1().buildTree(pre, in);
    }


    Map<Integer, Integer> inorderVal2IndexMap = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            int val = inorder[i];
            inorderVal2IndexMap.put(val, i);
        }
        return build(preorder, 0, preorder.length - 1, 0);
    }

    private TreeNode build(int[] preorder, int preorderLeft, int preorderRight, int inorderLeft) {
        if (preorderLeft > preorderRight) {
            return null;
        }
        int rootVal = preorder[preorderLeft];
        Integer inorderRootIndex = inorderVal2IndexMap.get(rootVal);
        int leftSubTreeLength = inorderRootIndex - inorderLeft;
        TreeNode root = new TreeNode(rootVal);
        root.left = build(preorder, preorderLeft + 1, preorderLeft + leftSubTreeLength,
                inorderLeft);

        root.right = build(preorder, preorderLeft + leftSubTreeLength + 1, preorderRight,
                inorderRootIndex + 1);
        return root;
    }

}
